\section{Descripci\'on del Problema}

En una competencia, los participantes tienen que atravesar puentes, pero cada puente consta de $n$ tablones. 
Algunos de esos tablones estan rotos (se sabe cuales de antemano). Adem\'as existe un n\'umero m\'aximo de tablones $numMax$ que cada participante puede atravesar de un solo salto.
Se nos pide dise\~nar un algoritmo que dado un n\'umero $n$ de tablones en un puente, $numMax$ el salto mas largo (m\'axima cantidad de tablones que se pueda atravesar de un salto), y un listado del estado de los tablones del puente, 
devuelva una secuencia con los tablones en los que hay que saltar (sin pisar ninguno roto) tal que se pueda atravesar el puente en una cantidad m\'inima de saltos (si existiera dicha soluci\'on).
\subsection{Ejemplo}
Una instancia del problema podr\'ia ser:
\begin{itemize}
\item $nTablones$ = 6, $saltoMax$ = 3.
\item Una secuencia $E$ que representa el estado de los tablones, $E= [0,0,1,1,0,1]$ donde la posici\'on \textit{i} de la secuencia representa el estado del tabl\'on \textit{i} (0=sano, 1=roto). 
\end{itemize}

Una posible soluci\'on ser\'ia:\\
$cantMinDeSaltos$ = 3  y los saltos son : $[2,5,(n+1)]$ donde cada n\'umero se interpreta como el tabl\'on (su posici\'on desde el comienzo del puente) sobre el que se hace el salto y ${n+1}$ es del otro lado del puente.
N\'otese que para poder atravesarlo necesariamente el \'ultimo valor de la secuencia soluci\'on tiene que ser $cantDeTablones + 1$.\\
\\
En cambio si consideramos la instancia:
\begin{itemize}
\item $nTablones$ = 6, $saltoMax$ = 3.
\item estado de los tablones: [0,0,0,1,1,0].
\end{itemize}
No tiene soluci\'on ya que la cantidad de tablones que se pueden atravesar como m\'aximo de un solo salto  es 3 y se necesita como m\'inimo atravesar 4 tablones de un solo salto para no caerse del puente.

\section{Idea General de la Resoluci\'on}
Decidimos implementar el algoritmo con la siguiente idea. 
Guardo los valores de entrada en un arreglo $entradas$ indexado por el $id$ de cada tabl\'on ($id_1: primerTablon,..., id_n: ultimoTablon$) en el que cada tabl\'on tiene en su posici\'on correspondiente el estado del mismo ($1=roto, 0=sano$). El arreglo tiene $n+2$ posiciones, siendo la posici\'on $0$ y la $n+1$ las correspondientes al inicio y final del puente respectivamente, estas dos posiciones por convenci\'on las consideramos como tablones sanos.\\
Luego llamamos a la funci\'on $ejecutar$ que va a recibir como par\'ametros el arreglo $entradas$ (antes mencionado) y un entero $saltoMax$ que representa la cantidad m\'axima de tablones que se pueden atravesar de un solo salto. La funci\'on $ejecutar$ es la que nos va a dar el resultado que nos interesa, y opera de la siguiente manera:

\begin{itemize}
 
\item La idea es recorrer el arreglo $entradas$ una sola vez e ir guardando en cada iteraci\'on tres valores: $poAEvaluar$, $posCandidata$ y $ultimaPosicion$, todos numeros enteros inicializados en 1, 0 y 0 respectivamente.
\item En cada iteraci\'on se hace lo siguiente: $posAEvaluar$ contiene la posici\'on actual del arreglo donde me encuentro parado, y si es un tabl\'on sano actualizo $posCandidata$ con ese valor.
\item Aumento en uno $posAEvaluar$.
\item Luego pregunto si desde $ultimaPosicion$ hasta $posAEvaluar$ supera el salto permitido ($saltoMax$), o si llegu\'e hasta el final del puente. En ese caso tengo 2 opciones:
\begin{itemize}
\item Si desde la ultima posici\'on hasta $posCandidata$ supere $saltMax$, yo s\'e que el problema no tiene soluci\'ion y termino.
\item Si no fuese as\'i, como la siguiente $posAEvaluar$ ya supera el l\'imite, yo se que lo m\'aximo que puedo saltar desde la $ultimaPosicion$ es $posCandidata$ as\'i que la agrego a la secuencia de la soluci\'on. Y sigo iterando.
\item Recordemos que $posAEvaluar$ se encuentra por revisar una posici\'on del puente que no la hemos visitado y que desde la actual $posCandidata$ hasta ah\'i no hay tablones sanos, porque sino, ya hubiesemos actualizado $posCandidata$, as\'i que sigo hacia adelante.
\end{itemize}
\item Si no caigo en el caso de que la siguiente posici\'on a evaluar no supera $saltoMax$ desde la $ultimaPosicion$, continuo la iteraci\'on
\end{itemize}

\subsection{Pseudoc\'odigo}
Vamos a desarrollar un pseudoc\'odigo de la funci\'on $ejecutar$ cuyos par\'ametros son: arreglo con estado de tablones ($entradas$), y salto m\'aximo de tablones ($saltMax$):

\begin{algorithmic}[1]\parskip=1mm
  \STATE{int posAEvaluar(1), posCandidata(0), ultimaPos(0)}
  \STATE{\textbf{for it = entradas.primero; it < entradas.final; it++}}
    \STATE{\quad Si *it es un tablon sano entonces}
		\STATE{\quad \quad $posCandidata = posAEvaluar$}
    \STATE{\quad $posAEvaluar$++}
    \STATE{\quad Si desde $ultiPos a posAEvaluar$ supera $saltMax$ o se llego al final}
		\STATE{\quad \quad Si desde $ultPos a posCandidata$ se supera $saltMax$}
			\STATE{\quad \quad \quad No tiene solucion, se detiene el ciclo y se sale del algoritmo}
		\STATE{\quad \quad $ultPos = posCandidata$}
		\STATE{\quad \quad Agregar $ultPos$ al vector solucion}
  \STATE{Devolver $vectorSolucion$}

\end{algorithmic}


\section{Correctitud y Complejidad}
Se nos pide que el algoritmo devuelva la menor cantidad de saltos que se pueda hacer para pasar el puente(si existe soluci\'on).
El algoritmo que hemos planteado realiza ese pedido:

\subsection{Correctitud}
En el  comienzo del algoritmo el siguiente tabl\'on es el tablon m\'as alejado hacia adelante del tabl\'on actual que se pueda saltar.
Supongamos que para alguna instancia con soluci\'on existente nuestro algoritmo devuelve la siguiente soluci\'on:
\\
$S1 = {t_1,...,t_i,...,t_k,...,t_m}$\\
Donde $S1$ es una secuencia de saltos y cada elemento $t_i$ es un tabl\'on (los tablones se identifican con un n\'umero entero positivo desde 1 hasta n). La secuencia muestra el orden de los saltos, y evidentemente, la longitud de la secuencia es la cantidad de saltos en esa soluci\'on.
El \'ultimo elemento $t_m$ representa el final del puente (considero tablon n+1).
\\
Supongamos tambi\'en que $S1$ no es la soluci\'on \'optima, entonces existe una soluci\'on $S2$ tal que la cantidad de saltos para atravesar el puente es menor que $S1$. 
Eso quiere decir: long($S2$) < long($S1$).\\
$S2 = {s_1,...,s_i,...,s_k}$  adem\'as $k < m$ y tambi\'en: $s_k$ = $t_m$ = $n+1$ ya que ambas secuencias tienen que terminar al final del puente.

Afirmo que para todo elemento \textit{i} con \textit{i} entre 1 y m : $s_i <= t_i$ en $S2$ y $S1$ respectivamente.\\
Demostraci\'on por inducci\'on en $i$:\\
C.B.(i=1) :
\begin{itemize}
\item $s_1 <= t_1$, es el primer salto y sino fuera asi, osea $s_1 > t_1$ ser\'ia absurdo ya que $t_1$ es el mayor salto que se puede dar sin pisar un tabl\'on roto.
\end{itemize}

Paso inductivo (quiero probar que: $s_{i+1} <= t_{i+1}$):
\begin{itemize}
\item H.I. = $s_i <= t_i$
\item supongo que no es as\'i, eso quiere decir que $t_{i+1} < s_{i+1}$.
\item en $S1$ el salto de $t_i$ a $t_{i+1}$ es el salto posible mas largo a partir del tabl\'on $t_i$ ($t_i < t_{i+1}$).
\item Entonces por H.I. $s_i <= t_i < t_{i+1} < s_{i+1}$, entonces en $S2$ el salto de $s_i$ a $s_{i+1}$ es mucho mayor que el salto de $t_i$ a $t_{i+1}$. 
\item Esto es absurdo ya que el algoritmo nos asegura que a partir de la posici\'on $t_i$ el algoritmo hace el salto mas largo posible.
\item Entonces $s_{i+1} <= t_{i+1}$
\end{itemize}

Ahora ya sabemos si comparamos cada elemento $s_i$ de la secuencia $S1$ con su respectivo elemento $s_i$ del mismo indice en $S2$, entonces $s_i <= t_i$.
Pero entonces $s_k <= t_k$ y sabemos que $s_k$ = $n+1$ por ser el \'ultimo elemento de $S2$, pero entonces en $S1$ ya hab\'ia llegado al otro lado del puente en $t_k$. Absurdo.
El absurdo vino de suponer que pod\'ia haber una soluci\'on con una cantidad de saltos menor a la de algoritmo. 

 
\subsection{Complejidad}

Calcular la complejidad de este algoritmo es muy sencillo:
\begin{itemize}
\item Para hallar el $T(n)$ (complejidad del algoritmo en funci\'on de $n$), donde $n$ es la cantidad de tablones que tiene el puente, tenemos que tener en cuenta 2 cosas principalmente: 
la primera la recepci\'on de par\'ametros $T_{recepcionDeEntradas}$  y la complejidad de $ejecutar$ que depende del tama\~no del vector que se le pase como par\'ametro $T_{ejecutar}$.
\item $T(n) =  T_{recepcionDeEntradas} + T_{ejecutar}$  =  $ MAX( T_{recepcionDeEntradas}, T_{ejecutar} )$.
\item $T_{recepcionDeEntradas}$ es $O(n)$ ya que se recepcionan n entradas + 2 (n cantidad de teblones) y a medida que las recepciona la guarda en el arreglo que ser\'a pasado como par\'ametro para llamar a $ejecutar$.
\item La funci\'on  $ejecutar$ recorre todo el arreglo una sola vez y en cada iteraci\'on realiza operaciones de comparaci\'on, suma o asignaci\'on que son operaciones en O(1), 
entonces como el tama\~no del arreglo es $n$, podemos decir que $T_{ejecutar}$ tambi\'en es O(n).
\item Entonces $T(n) = MAX (O(n), O(n)) $ = $O(n)$.
\item con lo cual $T(n) = O(n)$
\end{itemize}

La complejidad del algoritmo dado es de $O(n)$ ya que a lo sumo recorre la entrada dada en un loop simple. \\
\subsection{Test de Performance}
Como se puede ver en el gr\'afico, el cual fue generado con entradas aleatorias para cada N al cual se iba a evaluar (tanto el saltoMaximo y el valor de sal\'ud de cada tablon) y despues se corr\'ia 200 veces para mitigar el error que pudiera generarse en el computador. \\
\\
\includegraphics[scale=0.5]{imagenes/ej1.png} 
\\
El gr\'afico efectivamente arroja una linea que crece linealmente en funcion del tamaño de la entraday tiende que para el N 518000 la instanc\'ia tardar\'ia aproximadamente 1 sec. por lo tanto mi constante es $\frac{1}{518000}$, se agrego un constante adicional para compensar el pico en una serie de N que particularmente le costo calcular. Como dato curioso se puede observar en el grafico que hubo ciertos N en el cual el algoritmo tubo una respuesta casi instantanea, esto se puede atribuir a instancias aleatorias que justo coincid\'ia con el mejor caso o cerca que puede ser un saltoMax cercano a la cantidad de tablones totales. \\

